1. Field of the Invention
The present invention relates to the field of devices for interconnecting networks; and more particularly to bridge devices with self learning for interconnecting networks.
2. Description of Related Art
Increasingly, local area networks (LANs) are being used in computing applications. One type of LAN protocol is the Ethernet protocol. In the Ethernet protocol, a network is divided into various segments or "collision domains." Each network segment consists of multiple nodes. A node is a device on a network such as a terminal or a printer. The distance at which nodes in a segment can be located from other nodes is limited. For example, in "Fast Ethernet" within a segment may allow nodes to only be as far apart as 205 meters.
Two segments can be connected through a bridge device. The bridge isolates a collision domain so that a collision that occurs in one segment does not affect another segment. Once the collision domains of two segments are separated by a bridge, two nodes can be farther apart than they could have been had they been in the same collision domain.
Besides segmentation, another bridge function is filtering. The purpose of filtering is to block unwanted traffic of information from entering another segment and wasting bandwidth. A bridge passes information from one segment to another segment in the form of packets. Based on various criteria, a bridge does not forward some of the packets it receives. For example, a bridge and method for accessing data in a table and its application to the routing of data between remote stations is described in a patent application by Marshall, European Publication Number 0,365,337,A2, (application number 89310789.6) published Apr. 25, 1990. For example, inter-LAN connection equipment is described in U.S. Pat. No. 5,477,547 (Sugiyama).
One criterion is that if a packet is headed for another node within the same segment (local traffic), preferably the bridge should not forward the packet into another segment. To do this the bridge needs information as to whether particular nodes reside in particular segments. One way a bridge can obtain this information is by observing the source addresses of packets from each segment and storing the source addresses from packets from one segment in a source address table. When a packet arrives, a CPU has to search a table of many entries and compare the destination address with each of them. Alternatively, also using a CPU, the search and compare function may be performed with content addressable memory (CAM). Using a CAM requires extra hardware (the CAM) and is difficult or impossible to scale for networks having gigabyte per second speeds. An FDDI Bridge Frame Learning and Filtering Apparatus and Method where a source address is stored in a CAM is described in U.S. Pat. No. 5,481,540 (Gang).
Accordingly there is a need for efficient and lower cost searching in a bridge to determine whether a packet should be forwarded to another network segment.
If a bridge learns the location of nodes by storing information in tables, then the tables may no longer be accurate if nodes are subsequently moved. There is therefore a need for an apparatus and method to update the table in a bridge so that the tables reflect a more recent view of the location of nodes.
A table with information regarding source addresses may be indexed by means of a hash function. A hash function may be employed to index entries in a table for addresses. However, a problem with hash functions is that two addresses may map into the same hash value. For example, A Bridge Apparatus with an Address Check Circuit for Interconnecting Networks in which hashing is used is described in U.S. Pat. No. 5,247,620 (Fukuzawa).
Accordingly, there is a need for a device that helps to reduce the complexity and costs associated with a bridge and helps to more efficiently provide the functionality of interconnection between network media and helps to avoid leaks of local packets to other network segments and is scalable for higher speed networks.